/*!
 * \file OsterCliquer.h
 *
 * \date Jan 27, 2014
 * \author correa
 */
#ifndef OSTERCLIQUER_H_
#define OSTERCLIQUER_H_

#include <Cliquer.h>
#include <Doll.h>
#include <Grafo.h>
#include <VertexSet.h>

using namespace std;

/*!
 * \class OsterCliquer
 *
 * Implementación de Cliquer con el método de las muñecas rusas de Ostergard
 */
class OsterCliquer : public Cliquer
{
	const int		_n;
	const Grafo&	_grafo;
	VertexSet& 		_RR;
	VertexSet 		_WW;
	SingleNodeSet 	_nodeRR;
	SingleNodeSet 	_nodeR;
	SingleNodeSet 	_nodeW;
	Doll **			_stack;
	double *		_C;

	int greedyColoring(VertexSet& R, VertexSet& W, int lim);
	int greedyColoring(VertexSet& R);
	void maxStab(VertexSet& R, VertexSet& W, int u);
	int expClique(VertexSet& R, int * C, int * topC);

	int greedyColoring(VertexSet& R, const IntValueArray& pesos);
	int expClique(VertexSet& R, int * C, int * topC, const IntValueArray& pesos);

	double greedyColoring(VertexSet& R, const DoubleValueArray& pesos);
	double expClique(VertexSet& R, int * C, int * topC, const DoubleValueArray& pesos);

public:
	/*!
	 * Creates a solver for maximum clique or maximum stable set
	 *
	 * \param clqOrStab if \c true, this object finds a maximum clique in the graph; otherwise,
	 * it finds a clique in the complement (which means a maximum stable set in the graph)
	 */
	OsterCliquer(const Grafo &g, bool clqOrStab);
	~OsterCliquer();
	int optimize(const VertexSet &subgrafo, VertexSet &clique, int cotaInferior=0,
			int cotaSuperior=INT_MAX, int tolerancia=0);
	int optimize(const IntValueArray& pesos, const VertexSet &subgrafo,
			VertexSet &clique,
			int cotaInferior=0, int cotaSuperior=INT_MAX, int tolerancia=0);
	double optimize(const DoubleValueArray& pesos, const VertexSet &subgrafo,
			VertexSet &clique, double cotaInferior=0.0, double cotaSuperior=DBL_MAX, double tolerancia=0.0);
};

#endif /* OSTERCLIQUER_H_ */
